Unrank BinTree

List and Unrank for Binary Trees of a Given Number of Internal Nodes

  • Trees are represented by tuple.
  • The empty tree is represented by None
def listTree(n): if n == 0: return [None] else: res = [] for i in range(n): for g in listTree(i): for d in listTree(n-1-i): res.append((g,d)) return res 
       
for t in listTree(3): print t 
        
(None, (None, (None, None)))
(None, ((None, None), None))
((None, None), (None, None))
((None, (None, None)), None)
(((None, None), None), None)
 
       

Catalan numbers (slow algorithm, cached)
@cached_function def catalan(n): print "Calcul de catalan(%i)"%n if n == 0: return 1 else: return sum(catalan(i)*catalan(n-1-i) for i in range(n)) 
       
catalan(10) 
        
16796
[catalan(i) for i in range(10)] 
        
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
 
       

Unrank using cached Catalan
def unrankTree(n, i): if i >= catalan(n): raise ValueError, (n, i) elif n == 0: return None else: ng = 0 while i >= catalan(ng) * catalan(n-1-ng): i -= catalan(ng) * catalan(n-1-ng) ng += 1 ig = i // catalan(n-1-ng) id = i % catalan(n-1-ng) return (unrankTree(ng, ig), unrankTree(n-1-ng, id)) 
       
N=10 l = [unrankTree(N, i) for i in range(catalan(N))] l == listTree(N) 
        
True
N =100 
       
c = catalan(100) 
       
h = randint(0, c); h 
        
158330257917402900089066150980719099108736924660764718063L
unrankTree(N, h) 
        
((((None, None), None), (((None, (None, (None, ((None, (((None,
None), None), (None, (None, (None, None))))), ((None, (None, None)),
((None, None), ((((None, (((None, None), None), None)), (((None,
None), ((None, None), (((((((None, (None, None)), None), None),
(None, None)), None), (((((((None, ((None, None), None)), (None,
None)), (None, (None, None))), None), None), None), None)), (None,
(((((None, (((None, None), None), (((None, None), None), (None,
(None, (None, None)))))), ((None, None), None)), None), None),
(None, (None, (((((None, ((None, None), None)), (None, (((None,
None), (None, ((None, (None, None)), (None, None)))), ((None, None),
((None, None), None))))), None), None), ((None, None),
None))))))))), None)), (None, None)), None))))))), ((None, (None,
None)), None)), None)), None)
def prof(tr): if tr is None: return 0 else: return 1+max(prof(tr[0]), prof(tr[1])) 
       
prof(unrankTree(N, h)) 
        
27